package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月27日
*时间：下午5:57:25
*/
public class Q77 {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        if (A == null || A.length() <= 0 || B == null | B.length() <= 0) {
            return 0;
        }
        int n = A.length();
        int m = B.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
            	if(A.charAt(i-1) == B.charAt(j-1)){
            		dp[i][j] = dp[i-1][j-1]+1;
            	}else{
            		dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            	}
            }
        }
        return dp[n][m];
    }

    @Test
    public void testA() {
        String A = "";
        String B = "";
        System.out.println(longestCommonSubsequence(A, B));
    }

}
